MySQL索引详解(一文搞懂) |
您所在的位置:网站首页 › 数据库索引 原理 › MySQL索引详解(一文搞懂) |
1、什么是MySQL索引?官方上面说索引是帮助MySQL高效获取数据的数据结构,通俗点的说,数据库索引好比是一本书的目录,可以直接根据页码找到对应的内容,目的就是为了加快数据库的查询速度。索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。一种能帮助mysql提高了查询效率的数据结构:索引数据结构。1.1、索引原理 索引的存储原理大致可以概括为一句话:以空间换时间。 一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往是存储在磁盘上的文件中的(可能存储在单独的索引文件中,也可能和数据一起存储在数据文件中)。 数据库在未添加索引进行查询的时候默认是进行全文搜索,也就是说有多少数据就进行多少次查询,然后找到相应的数据就把它们放到结果集中,直到全文扫描完毕。 1.2、索引的分类主键索引:primary key 设定为主键后,数据库自动建立索引,InnoDB为聚簇索引,主键索引列值不能为空(Null)。唯一索引: 索引列的值必须唯一,但允许有空值(Null),但只允许有一个空值(Null)。复合索引: 一个索引可以包含多个列,多个列共同构成一个复合索引。全文索引: Full Text(MySQL5.7之前,只有MYISAM存储引擎引擎支持全文索引)。全文索引类型为FULLTEXT,在定义索引的列上支持值的全文查找允许在这些索引列中插入重复值和空值。全文索引可以在Char、VarChar 上创建。空间索引: MySQL在5.7之后的版本支持了空间索引,而且支持OpenGIS几何数据模型,MySQL在空间索引这方年遵循OpenGIS几何数据模型规则。前缀索引: 在文本类型为char、varchar、text类列上创建索引时,可以指定索引列的长度,但是数值类型不能指定。1.3、索引的优缺点优点: 大大提高数据查询速度。可以提高数据检索的效率,降低数据库的IO成本,类似于书的目录。通过索引列对数据进行排序,降低数据的排序成本降低了CPU的消耗。被索引的列会自动进行排序,包括【单例索引】和【组合索引】,只是组合索引的排序需要复杂一些。如果按照索引列的顺序进行排序,对order 不用语句来说,效率就会提高很多。缺点: 索引会占据磁盘空间。索引虽然会提高查询效率,但是会降低更新表的效率。比如每次对表进行增删改查操作,MySQL不仅要保存数据,还有保存或者更新对应的索引文件。维护索引需要消耗数据库资源。综合索引的优缺点: 数据库表中不是索引越多越好,而是仅为那些常用的搜索字段建立索引效果最佳!1.4、创建索引的基本操作创建主键索引: #建表时,主键默认为索引 create table user( id varchar(11) primary key, name varchar(20), age int ) #查看user表中的索引 show index from user;创建单列索引: #创建单列索引,只能包含一个字段 create index name_index on user(name);创建唯一索引: #创建唯一索引,只能有一个列 create unique index age_index on user(age);创建符合索引: #复合索引 create index name_age_index on user(name,age);满足复合索引的查询的两大原则:**假如创建的复合索引为三个字段,按顺序分别是(name,age,sex)在查询时能利用复合索引的查询条件如下:** 1、最左前缀原则(如下四种都满足条件) select * from user where name = ? select * from user where name = ? and age = ? select * from user where name = ? and sex = ? select * from user where name = ? and age = ? and sex = ?1.1、如下是不满足最前左缀的条件(但是不是全部都不生效,如下第2原则解释) select * from user where name = ? and sex = ? and age = ? select * from user where age = ? and sex = ? and name = ? select * from user where sex = ? and age = ? and name = ? select * from user where age = ? and sex = ? …………等等2.MySQL 引擎在执行查询时,为了更好地利用索引,在查询过程中会动态调整查询字段的顺序!(也就是说,当条件中的字段全部达到复合索引中的字段时,可以动态调整字段顺序,使其满足最前左缀) #可以使用复合索引:索引中包含的字段数都有,只是顺序不正确,在执行的时候可以动态调整为最前左缀 select * from user where sex = ? and age = ? and name = ? select * from user where age = ? and sex = ? and name = ? #不可以使用复合索引:因为缺少字段,并且顺序不正确 select * from user where sex = ? and age = ? select * from user where age = ? and name = ? select * from user where age = ? select * from user where sex = ? 2、索引的数据结构本文借鉴丙哥文章:一文搞懂MySQL索引所有知识点MySQL索引使用的数据结构主要有BTree索引和hash索引。 对于hash索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景建议选择BTree索引。 2.1、根据存储引擎的不同,实现方式也不同MySQL的索引数据结构最常使用的是B树中的B+Tree,但对于主要的两种存储引擎的实现方式是不同的。 ==InnoDB中data阈存储的是行数据,而MyISAM中存储的是磁盘地址。==MyISAM: B+Tree叶节点的data域存放的是数据记录的地址。在索引检索的时候,首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则根据data域中磁盘地址到磁盘中寻址定位到对应的磁盘块,然后读取相应的数据记录,这被称为“非聚簇索引”。InnoDB: ==其数据文件本身就是索引文件==。相比MyISAM,索引文件和数据文件是分离的,其表数据文件本身就是按照B+Tree组织的一个索引结构,树的叶节点data域保存了完整的数据记录。这个索引的Key是数据表的主键,因此InnoDB表数据文件本身就是主索引。这被称为“聚簇索引(聚集索引)”。而其余的索引都作为辅助索引,辅助索引的data域存储相应记录主键的值而不是地址,这也是和MyISAM不同的地方。在根据主索引搜索时,直接找到Key所在的节点即可取出数据;在根据辅助索引查找时,则需要先取出主键的值,再走一遍主索引。因此在设计表的时候,不建议使用过长的字段作为主键,也不建议使用非单调的字段作为主键,这样会造成主索引频繁分裂。2.2、Hash表Hash表,在Java中的HashMap,TreeMap就是Hash表结构,以键值对的形式存储数据。我们使用hash表存储表数据结构,Key可以存储索引列,Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高,时间复杂度为O(1);但是不支持范围快速查找,范围查找时只能通过扫描全表的方式,筛选出符合条件的数据。 显然这种方式,不适合我们经常需要查找和范围查找的数据库索引使用。 2.3、二叉树
二叉树的特点就是为了保证每次查找都可以进行折半查找,从而减少IO次数。 但是二叉树不是一直保持二叉平衡,因为二叉树很考验根节点的取值,因为很容易在某个节点下不分叉了,这样的话二叉树就不平衡了,也就没有了所谓的能进行折半查找了,如下图:
平衡二叉树采用的是二分法思维,平衡二叉查找树除了具备二叉树的特点,最主要的特征是树的左右两个子树的层级最多差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。 使用平衡二叉查找树查询的性能接近与二分查找,时间复杂度为O(log2n),查询id=6,只需要两次IO。 MySQL的数据是存储在磁盘文件中的,查询处理数据时,需要先把磁盘中的数据加载到内存中,磁盘IO操作非常耗时,所以我们优化的重点就是尽量减少磁盘的IO操作。访问二叉树的每个节点都会发生一次IO,如果想要减少磁盘IO操作,就需要尽量降低树的高度。 那如何降低树的高度呢? 假如key为bigint=8字节,每个节点有两个指针,每个指针为4个字节,一个节点占用的空间为(8+4*2=16)。 因为在MySQL的InnoDB引擎的一次IO操作会读取一页的数据量(默认一页大小为16K),而二叉树一次IO操作的有效数据量只有16字节,空间利用率极低。为了最大化的利用一次IO操作空间,一个解决方法就是在一个节点处存储多个元素,在每个节点尽可能多的存储数据。每个节点可以存储1000个索引(16k/16=1000),这样就将二叉树改造成了多叉树,通过增加树的分叉树,将树的体型从高瘦变成了矮胖。构建1百万条数据,树的高度需要2层就可以(1000*1000=1百万),也就是说只需要两次磁盘IO操作就可以查询到数据,磁盘IO操作次数变少了,查询数据的效率整体也就提高了。 这种数据结构我们称之为B树,==B树是一种多叉平衡查找树==,如下图主要特点: B树的节点中存储这多个元素,每个内节点有多个分叉。节点中的元素包含键值和数据,节点中的键值从大到小排列。也就是说,在所有的节点中都存储数据。父节点当中的元素不会出现在子节点中。所有的叶子节点都位于同一层,叶子节点具有相同的深度,叶子节点之间没有指针连接。B树数据结构大致如下: 过程如下图所示: B+树,作为B树的升级版,MySQL在B树的基础上继续进行改造,使用B+树构建索引。B+树和B树最主要的区别在于==非叶子节点是否存储数据==的问题。 B树:叶子节点和非叶子节点都会存储数据。B+树:只有叶子节点才会存储数据,非叶子节点只存储键值key;叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表。B+树的大致数据结构: 等值查询实例: 假如我们要查询key为9对应的数据data,查询路径为:磁盘块1->磁盘块2->磁盘块6。 第一次磁盘IO:将磁盘块1加载到内存中,在内存中从头遍历比较,9磁盘块7前三次磁盘IO:首先查找到键值为9对应的数据(定位到磁盘块6),然后缓存大结果集中。这一步和前面等值查询流程一样,发生了三次磁盘IO。继续查询,查找到节点15之后,底层的所有叶子节点是一个有序列表,我们从磁盘块6中的键值9开始向后遍历筛选出所有符合条件的数据。第四次磁盘IO:根据磁盘块6的后继指针到磁盘中寻址定位到磁盘块7,将磁盘块7加载到内存中,在内存中从头遍历比较,9 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |